import bisect
class Solution(object):
    def maximumBeauty(self, flowers, newFlowers, target, full, partial):
        flowers.sort()
        n = len(flowers)
        prefix = flowers.copy()
        for i in range(1, n):
            prefix[i] += prefix[i - 1]
        tx = [max(target - t, 0) for t in flowers]
        tx.reverse()
        for i in range(1, n):
            tx[i] += tx[i - 1]
        min_val = min(flowers)
        max_val = target
        ans = 0
        for val in range(min_val, max_val):
            index = bisect.bisect_left(flowers, val)
            if index == 0:
                part1 = 0
            else:
                part1 = val * index - prefix[index - 1]
            if part1 > newFlowers:
                break
            left_f = newFlowers - part1
            index2 = bisect.bisect_right(tx, left_f)
            if index2 < n - index:
                ans = max(ans, val * partial + min(index2, n - 1) * full)
            else:
                if n - index > 0:
                    part2 = tx[n - index - 1]
                else:
                    part2 = 0
                left_f = newFlowers - part1 - part2
                ans = max(ans, val * partial + full * min(left_f // (target - val) + n - index, n - 1))
        if tx[-1] <= newFlowers:
            ans = max(ans, full * n)
        return ans


data = Solution()
flowers = [1,3,1,1]
newFlowers = 7
target = 6
full = 12
partial = 1
print(data.maximumBeauty(flowers, newFlowers, target, full, partial))
flowers = [1, 8, 14, 17, 18, 20]
newFlowers = 48
target = 20
full = 3
partial = 4
print(data.maximumBeauty(flowers, newFlowers, target, full, partial))


